<!--
 * @Author: your name
 * @Date: 2021-07-17 11:48:36
 * @LastEditTime: 2021-07-18 01:26:49
 * @Description: 
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>封装双向链表</title>
</head>

<body>
    <script>
        function DoublyLinkedList() {
            // 内部的类：节点类
            function Node(data) {
                this.data = data
                this.prev = null
                this.next = null
            }

            // 属性
            this.head = null
            this.tail = null
            this.length = 0

            // 1. 追加方法
            DoublyLinkedList.prototype.append = function (data) {
                // 1. 创建新节点
                var newNode = new Node(data)
                // 2.判断添加的是否是第一个节点
                if (this.length === 0) { // 2.1 是第一个节点
                    this.head = newNode
                    this.tail = newNode
                } else {                // 2.2 不是第一个节点
                    newNode.prev = this.tail
                    this.tail.next = newNode
                    this.tail = newNode
                }
                // 3. length + 1
                this.length += 1
            }

            // 2. 将链表转换为字符串
            // 2.1 toString 方法
            DoublyLinkedList.prototype.toString = function () {
                return this.backwardString()
            }

            // 2.2 forwardString 方法
            DoublyLinkedList.prototype.forwardString = function () {
                // 定义变量
                var current = this.tail
                var resultString = ''

                // 依次向前遍历，获取前一个节点
                while (current) {
                    resultString += current.data + ' '
                    current = current.prev
                }

                return resultString
            }

            // 2.3 backwardString 方法
            DoublyLinkedList.prototype.backwardString = function () {
                // 1. 定义变量
                var current = this.head
                var resultString = ''

                // 2. 依次向后遍历，获取每一个节点
                while (current) {
                    resultString += current.data + ' '
                    current = current.next
                }
                return resultString
            }

            // 3. insert方法
            DoublyLinkedList.prototype.insert = function (position, data) {
                // 1. 越界判断
                if (position < 0 || position > this.length) return false

                // 2. 根据data创建新的节点
                var newNode = new Node(data)

                // 3. 判断原列表是否为空
                if (this.length === 0) {
                    this.head = newNode
                    this.tail = newNode
                } else {
                    if (position === 0) { // 3.1 判断position是否为0
                        this.head.prev = newNode
                        newNode.next = this.head
                        this.head = newNode
                    } else if (position === this.length) { // 3.2 向最后插入
                        newNode.prev = this.tail
                        this.tail.next = newNode
                        this.tail = newNode
                    } else { // 3.3 其它地方插入
                        var current = this.head
                        var index = 0

                        while (index++ < position) {
                            current = current.next
                        }

                        // 修改指针
                        newNode.next = current
                        newNode.prev = current.prev
                        current.prev.next = newNode
                        current.prev = newNode
                    }
                }
                // 4. length + 1
                this.length += 1
            }

            // 4. get方法
            DoublyLinkedList.prototype.get = function (position) {
                // 1. 越界判断
                if (position < 0 || position >= this.length) return null

                // this.length / 2 > position
                // this.length / 2 < position
                if (this.length / 2 > position) { // 从前往后查找
                    // 2. 获取元素
                    var current = this.head
                    var index = 0
                    while (index++ < position) {
                        current = current.next
                    }
                    return current.data
                } else { // 从后往前查找
                    // 2. 获取元素
                    var current = this.tail
                    var index = this.length - 1
                    while (index-- > position) {
                        current = current.prev
                    }

                    return current.data
                }


            }

            // 5. indexOf方法
            DoublyLinkedList.prototype.indexOf = function (data) {
                // 1. 定义变量
                var current = this.head
                var index = 0

                // 查找和data相同的节点
                while (current) {
                    if (current.data === data) {
                        return index
                    }
                    current = current.next
                    index += 1
                }

                return -1
            }

            // 6. update方法
            DoublyLinkedList.prototype.update = function (position, newData) {
                // 1. 越界判断
                if (position < 0 || position >= this.length) return false

                if (this.length / 2 > position) {// 从前往后找
                    // 2.寻找正确的节点
                    var current = this.head
                    var index = 0
                    while (index++ < position) {
                        current = current.next
                    }

                    current.data = newData
                } else { // 从后往前找
                    // 2.寻找正确的节点
                    var current = this.tail
                    var index = this.length - 1
                    while (index-- > position) {
                        current = current.prev
                    }

                    current.data = newData
                }
                return true
            }

            // 7. removeAt
            DoublyLinkedList.prototype.removeAt = function (position) {
                // 1. 越界判断
                if (position < 0 || position >= this.length) return null

                // 2. 判断是否只有一个节点
                var current = this.head
                if (this.length === 1) {
                    this.head = null
                    this.tail = null
                } else {
                    if (position === 0) {// 判断是否删除的是第一个节点
                        this.head.next.prev = null
                        this.head = this.head.next
                    } else if (position === this.length - 1) { // 删除最后一个节点
                        current = this.tail
                        this.tail.prev.next = null
                        this.tail = this.tail.prev
                    } else { // 删除其它节点
                        var index = 0
                        while (index++ < position) {
                            current = current.next
                        }
                        current.prev.next = current.next
                        current.next.prev = current.prev
                    }
                }
                // 3. length -1
                this.length -= 1
                return current.data
            }

            // 8. remove
            DoublyLinkedList.prototype.remove = function (data) {
                // 1. 根据data获取下标值
                var index = this.indexOf(data)

                // 2. 根据index删除对应位置的节点
                return this.removeAt(index)
            }


            // 9. isEmpty方法
            DoublyLinkedList.prototype.isEmpty = function () {
                return this.length === 0
            }

            // 10. size方法
            DoublyLinkedList.prototype.size = function () {
                return this.length
            }

            // 11. 获取链表的第一个元素
            DoublyLinkedList.prototype.getHead = function () {
                return this.head.data
            }

            // 12. 获取链表的最后一个元素
            DoublyLinkedList.prototype.getTail = function () {
                return this.tail.data
            }
        }




        var list = new DoublyLinkedList()
        list.append('abc')
        list.append('cba')
        list.append('nba')

        // console.log(list)
        // console.log(list.backwardString())
        // console.log(list.forwardString())
        // list.insert(0, 'aaa')
        // list.insert(4, 'bbb')
        // list.insert(2, 'ccc')
        // alert(list.get(0))
        // alert(list.get(2))
        // alert(list.get(5))
        // console.log(list.remove('cba'))
        // alert(list)

    </script>
</body>

</html>